package com.ww.springboot.boot.algorithm.tree;

import lombok.Data;

/**
 * 基本数结构
 * <p>
 * 值 左节点 右节点
 */
@Data
public class TreeNode<T> {
    private T val;
    private TreeNode left;
    private TreeNode right;

    public TreeNode() {
    }

    TreeNode(T val) {
        this.val = val;
    }

    TreeNode(T val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    /**
     * 二叉搜索数插入元素
     *
     * @param num
     * @return
     */
    public static boolean insert(int num, TreeNode<Integer> treeNode) {
        if (treeNode == null || treeNode.getVal() == null) {
            treeNode.setVal(num);
        } else if (treeNode.getVal() == num) {
            return false;
        } else if (treeNode.getVal() > num) {
            if (treeNode.getLeft() == null) {
                treeNode.setLeft(new TreeNode(num));
            } else {
                return insert(num, treeNode.getLeft());
            }
        } else {
            if (treeNode.getRight() == null) {
                treeNode.setRight(new TreeNode(num));
            } else {
                return insert(num, treeNode.getRight());
            }
        }
        return true;
    }


    /**
     * 二叉搜索数查询元素
     *
     * @param num
     * @return
     */
    public static boolean find(int num, TreeNode<Integer> treeNode) {
        if (treeNode == null || treeNode.getVal() == null) {
            return false;
        }
        while (treeNode.getRight() != null || treeNode.getLeft() != null) {
            if (treeNode.getVal() == num) {
                return true;
            } else if (treeNode.getVal() > num) {
                treeNode = treeNode.getLeft();
            } else {
                treeNode = treeNode.getRight();
            }
        }
        if (treeNode.getVal() == num) {
            return true;
        }
        return false;
    }
}